#include "TK.h"
bool sort(int n,int array[],char *name,char **argv){
	if((strcmp(argv[1],"-h")&&strcmp(argv[1],"--help")) == 0)
	{
		printf(" -h --help\t\toption reference. \n ");
		printf("-B --bubble\t\tsort the data by the way of Bubble Sort.\n ");
		printf("-i --insert\t\tsort the data by the way of Insertion Sort.\n ");
		printf("-s --select\t\tsort the data by the way of Selection Sort.\n ");
		printf("-m --merge\t\tsort the data by the way of Merge Sort.\n ");
		printf("-q --quick\t\tsort the data by the way of Quick Sort.(recommend!)\n ");
		printf("-c --count\t\tsort the data by the way of Counting Sort.\n ");
		printf("-r --radix\t\tsort the data by the way of Radix Sort.\n ");
		printf("-b --bucket\t\tsort the data by the way of Bucket Sort.\n ");
		printf("-H --heap\t\tsort the data by the way of Heap Sort.\n ");
		return false;
	}

	else if((strcmp(argv[1],"-B")&&strcmp(argv[1],"--bubble")) == 0)
		Bubble(n,array,name);
	else if((strcmp(argv[1],"-i")&&strcmp(argv[1],"--insert")) == 0)
		Insert(n,array,name);
	else if((strcmp(argv[1],"-s")&&strcmp(argv[1],"--select")) == 0)
		Select(n,array,name);
	else if((strcmp(argv[1],"-m")&&strcmp(argv[1],"--merge")) == 0)
		Merge(n,array,name);
	else if((strcmp(argv[1],"-q")&&strcmp(argv[1],"--quick")) == 0)
		Quick(n,array,name);
	else if((strcmp(argv[1],"-c")&&strcmp(argv[1],"--count")) == 0)
		Count(n,array,name);
	else if((strcmp(argv[1],"-r")&&strcmp(argv[1],"--radix")) == 0)
		Radix(n,array,name);
	else if((strcmp(argv[1],"-b")&&strcmp(argv[1],"--bucket")) == 0)
		Bucket_case2(n,array,name);
	else if((strcmp(argv[1],"-H")&&strcmp(argv[1],"--heap")) == 0)
		Heap(n,array,name);
	else
	{
		printf("please type the type of sort!");
		return false;
	}
	return true;
}

void Bubble(int n,int array[],char *name){
//	strcpy(argv[1],"bubble");//X characters at most. X is the size of original argv[1].
	strcpy(name,"bubble");
	int i,j,tmp,flag;
	for(i=0;i<n;i++)
	{
		flag = 0;
		for(j=0;j<n-i-1;j++)
		{

			if(array[j]>array[j+1])
			{
				tmp = array[j];
				array[j] = array[j+1];
				array[j+1] = tmp;
				flag = 1;
			}
		}
		if(!flag)
		{
			printf("There is no swap. Sort Accomplished in advance.\n");
			break;
		}
	}
}

void Insert(int n,int array[],char *name){
	strcpy(name,"insertion");
	int i,j,value;
/*	for(i=1;i<n;i++)
	{
		for(j=i;j>=0;j--)
		{	
			if(j==0||array[i]>=array[j-1])
			{
				if(j == i)
				break;

				val = array[i];

				for(k=i;i>j;i--,k--)
				array[i] = array[k-1];

				array[j] = val;
				break;
			}
		}
	}*/ //low efficiency 
	if(n<=1) return;
	for(i=1;i<n;i++)
	{
		value = array[i];
		for(j=i-1;j>=0;j--)
		{	
			if(array[j]>value)
			{
				array[j+1] = array[j];
			}
			else
			break;
		}
		array[j+1] = value;
	}
} 

void Select(int n,int array[],char *name){
	strcpy(name,"selection");
	int i,j,k,min;
	for(i=0;i<n;i++)
	{
		min = array[i];
		j = i;
		k = i;
		for(;k<n-1;k++)
		{
			if(min>array[k+1])
			{
				min = array[k+1];
				j = k+1;
			}
		}
		for(;j>i;j--)
		{
			array[j] = array[j-1];
		}	
		array[i] = min;
	}
}

void Merge(int n,int array[],char *name){
	strcpy(name,"merge");
	merge_recursion(array,0,n-1);
}

void merge_recursion(int array[],int p,int r){
	if(p>=r) return;
	int q = (p+r)/2;
	
	merge_recursion(array,p,q);
	merge_recursion(array,q+1,r);

	merge(array,p,q,r);
}

void merge(int array[],int p,int q,int r){
	int tmp[r-p+1];
	int i=p,j=q+1,k=0;
	int a,b;
	for(;i<=q&&j<=r;)
	{
		if(array[i]<=array[j])
		tmp[k++] = array[i++];
		else
		tmp[k++] = array[j++];	
	}

	for(;i<=q;)
	{
		tmp[k++] = array[i++];
	}
	for(;j<=r;)
	{
		tmp[k++] = array[j++];
	}
	for(k=0;k<r-p+1;k++)
	{
		array[p+k] = tmp[k];
	}
}

void Quick(int n,int array[],char *name){
	strcpy(name,"quick");
	quick_recursion(array,0,n-1);
}

void quick_recursion(int array[],int p,int r){
	if(p>=r) return;
	int q = partition(array,p,r);
	
	quick_recursion(array,p,q-1);
	quick_recursion(array,q+1,r);	
}

int partition(int array[],int p,int r){
	int tmp;
	int pivot = array[r];//we regard the last figure of array as a pivot.But this pivot is usually not a middle one so that the pivot tend to be unpredictable where it is.The result will be unfortunate,if the pivot is close to the verge of the array,which the complexity of quick_sort will degenerate into O(n2).
	for(int i=p;i<r;i++)
	{
		if(array[i]<pivot)
		{
			tmp = array[i];
			array[i] = array[p];
			array[p] = tmp;    
			p++;        
		}
	}
			tmp = array[r];
			array[r] = array[p];
			array[p] = tmp;   
	return p;//the return is not a value of pivot but the footnote of the pivot after swap. 
}

void Bucket_case2(int n,int array[],char *name){
	strcpy(name,"bucket");
	int *bucket = (int *)malloc(N*sizeof(int));
	int i,j;
	for(i=0;i<N;i++)
	bucket[i] = 0;
	for(i=0;i<n;i++)
	bucket[array[i]]++; 
	for(i=0,j=0;i<N;i++)
	{
		while(bucket[i]--)
		array[j++] = i;
	}
	free(bucket);
}

void Count(int n,int array[],char *name){
	strcpy(name,"count");
	int flag = 0;
	Isminus(n,array,&flag);
	int max = get_max(n,array)+1;
	int *count = (int *)malloc(max*sizeof(int));
	int i,sum;
	for(i=0;i<max;i++)
	count[i] = 0;
	for(i=0;i<n;i++)
	count[array[i]]++;
	for(sum=0,i=0;i<max;i++)
	{
		count[i+1] += count[i];	
	}
	int *tmp = (int *)malloc(n*sizeof(int));
	for(i=n-1;i>=0;i--)
	{
		tmp[count[array[i]]-1] = array[i];
		count[array[i]]--;
	}
	for(i=0;i<n;i++)
	{	
		if(flag)
		tmp[i] += flag;
		array[i] = tmp[i];
	}
	free(count);
	free(tmp);
}

int get_max(int n,int *array){
	int i;
	int max = array[0];
	for(i=0;i<n;i++)
	{
		if(array[i]>max)
		max = array[i];
	}
	return max;
}

int get_min(int n,int *array){
	int i;
	int min = array[0];
	for(i=0;i<n;i++)
	{
		if(array[i]<min)
		min = array[i];
	}
	return min;
}

void Isminus(int n,int *array,int *flag){
	int i;
	int min = get_min(n,array);
	if(min<0)
	{
		for(i=0;i<n;i++)
		array[i] -= min;	
		*flag = min;
	}
}

void Radix(int n,int array[],char *name){
	int i,j,m,k,lowbit,maxbit;
	int *size = (int *)malloc(10*sizeof(int *));
	int **bucket = (int **)malloc(10*sizeof(int *));
	for(i=0;i<10;i++)
	{
		bucket[i] = (int *)malloc(n*sizeof(int *));
		size[i] = 0;
	}

	int flag = 0;
	Isminus(n,array,&flag);//minus supported.

	maxbit = get_bit(get_max(n,array));
	for(m=0;m<maxbit;m++)
	{
		k = 0;
		for(i=0;i<n;i++)
		{
			lowbit = get_lowbit(array[i],m+1);
			bucket[lowbit][size[lowbit]++] = array[i];	
		}
		for(i=0;i<10;i++)
		{
			for(j=0;j<size[i];j++)
			{
				array[k++] = bucket[i][j];
			}
			size[i] = 0;
		}
	}

	for(i=0;i<n;i++)//minus supported.
	{	
		if(flag)
		array[i] += flag;
	}

	strcpy(name,"radix");		
	for(int i=0;i<10;i++)
	{
		free(bucket[i]);
	}
	free(bucket);
	free(size);
}

int get_bit(int num){
	int count = 0;
	while(num)
	{
		count++;
		num /= 10;	
	}
	return count;
	
}

int get_lowbit(int num,int bit){
	while(--bit)
	num /= 10;
	return num%10;
}

void Heap(int n,int *array,char *name){
	strcpy(name,"heap");
	buildheap(n,array);
/*	for(int k=0;k<n-1;k++)
	{
		swap(array,1,n-k);
		heapify(array,1,n-k-1);
	}*/
	int k = n;
	while(k>1)
	{
		swap(array,1,k);
		k--;
		heapify(array,1,k);
	}
}

void buildheap(int n,int *array){
	for(int i=n/2;i>0;i--)
	{
		heapify(array,i,n);
	}
}

void swap(int *array,int i,int j){
	int temp = array[i];
	array[i] = array[j];
	array[j] = temp;
}

void heapify(int *array,int i,int n){
	while(1)
	{
		int maxPos = i;
		if(2*i <= n && array[i] < array[2*i]) maxPos = 2*i;
		if(2*i+1 <= n && array[maxPos] < array[2*i+1]) maxPos = 2*i+1;
		if(maxPos == i)
		break;
		swap(array,maxPos,i);
		i = maxPos;
	}
}
